#include <bits/stdc++.h>

using namespace std;

class Solution{
public:
    vector<int> findXSum(vector<int>&nums,int k,int x){
        int n=nums.size(); vector<int> ans;
        for(int i=0;i+k<=n;i++){
            unordered_map<int,int>cnt;
            for(int j=0;j<k;j++)cnt[nums[i+j]]++;
            vector<pair<int,int>> vec;
            for(auto &p:cnt) vec.push_back({p.second,p.first});
            sort(vec.begin(),vec.end(),greater<pair<int,int>>());
            int sm=0;
            for(int j=0;j<x&&j<vec.size();j++)sm+=vec[j].first*vec[j].second;
            ans.push_back(sm);
        } return ans;
    }
};

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(): val(0), left(nullptr), right(nullptr){}
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
    TreeNode(int x,TreeNode *left,TreeNode *right): val(x), left(left), right(right){};
};
class Solution2{
public:
    int kthLargePerfectSubtree(TreeNode* root, int k){
        vector<int> vec;
        function<int(TreeNode *node)> dfs=[&](TreeNode *node)->int{
            if(node== nullptr) return 0;
            int l=dfs(node->left), r=dfs(node->right);
            if(l==r && l>=0 && r>=0){
                vec.push_back((1<<(l+1))-1);
                return l+1;
            } else return -1;
        };
        dfs(root);
        sort(vec.begin(),vec.end(),greater<int>());
        if(k>vec.size()) return -1;
        else return vec[k-1];
    }
};

class Solution3 {
public:
    int countWinningSeq(string s){
        const int MOD=1e9+7;
        int mp[128]; mp['F']=0; mp['W']=1; mp['E']=2;
        int n=s.length();
        vector<int> pow2((n+1)/2); pow2[0]=1;
        for(int i=1;i<pow2.size();i++) pow2[i]=pow2[i-1]*2%MOD;
        vector<vector<array<int,3>>> memo(n,vector<array<int,3>>(n*2+1,{-1,-1,-1}));
        auto dfs=[&](auto&& dfs, int i,int j, int ban)->int{
            if(-j>i) return 0;
            if(j>i+1) return pow2[i+1];
            int& res=memo[i][j+n][ban];
            if(res!=-1) return res;
            res=0;
            for(int k=0;k<3;k++) {
                if (i == n - 1 || k != ban) {
                    int score = (k - mp[s[i]] + 3) % 3;
                    if (score == 2) score = -1;
                    res = (res + dfs(dfs, i - 1, j + score, k)) % MOD;
                }
            }
            return res;
        };
        return dfs(dfs,n-1,0,0);
    }
};

#define ll long long
struct Magic {
    int K;
    typedef pair<int, int> pii;
    multiset<pii> st1, st2;
    long long sm1;

    Magic(int K): K(K) {
        sm1 = 0;
    }

    void adjust() {
        while (!st2.empty() && st1.size() < K) {
            pii p = *(st2.begin());
            st1.insert(p); sm1 += 1LL * p.first * p.second;
            st2.erase(st2.begin());
        }
        while (st1.size() > K) {
            pii p = *prev(st1.end());
            st2.insert(p);
            st1.erase(prev(st1.end())); sm1 -= 1LL * p.first * p.second;
        }
    }

    void add(pii p) {
        if (!st2.empty() && p >= *(st2.begin())) st2.insert(p);
        else st1.insert(p), sm1 += 1LL * p.first * p.second;
        adjust();
    }

    void del(pii p) {
        auto it = st1.find(p);
        if (it != st1.end()) st1.erase(it), sm1 -= 1LL * p.first * p.second;
        else st2.erase(st2.find(p));
        adjust();
    }
};
//class Solution4{
//public:
//    vector<ll> findXSum(vector<int>&nums,int k,int x){
//        int n=nums.size(); vector<ll> ans; unordered_map<int,int> cnt;
//        Magic magic(x);
//        for(int i=0;i<k;i++)cnt[nums[i]]++;
//        for(auto &p:cnt) magic.add({-p.second,-p.first});
//        for(int i=0;;i++){
//            ans.push_back(magic.sm1);
//            if(i+k==n) break;
//            magic.del({-cnt[nums[i]],-nums[i]});
//            cnt[nums[i]]--;
//            if(cnt[nums[i]]>0)magic.add({-cnt[nums[i]],-nums[i]});
//            if(cnt[nums[i+k]]>0)magic.del({-cnt[nums[i+k]], -nums[i+k]});
//            cnt[nums[i+k]]++;
//            magic.add({-cnt[nums[i+k]],-nums[i+k]});
//        } return ans;
//    }
//};

class Solution4 {
public:
    vector<long long> findXSum(vector<int>& nums, int k, int x) {
        using pii = pair<int, int>; // 出现次数，元素值
        set<pii> L, R;
        long long sum_l = 0; // L 的元素和
        unordered_map<int, int> cnt;
        auto add = [&](int x) {
            pii p = {cnt[x], x};
            if (p.first == 0) {
                return;
            }
            if (!L.empty() && p > *L.begin()) { // p 比 L 中最小的还大
                sum_l += (long long) p.first * p.second;
                L.insert(p);
            } else {
                R.insert(p);
            }
        };
        auto del = [&](int x) {
            pii p = {cnt[x], x};
            if (p.first == 0) {
                return;
            }
            auto it = L.find(p);
            if (it != L.end()) {
                sum_l -= (long long) p.first * p.second;
                L.erase(it);
            } else {
                R.erase(p);
            }
        };
        auto l2r = [&]() {
            pii p = *L.begin();
            sum_l -= (long long) p.first * p.second;
            L.erase(p);
            R.insert(p);
        };
        auto r2l = [&]() {
            pii p = *R.rbegin();
            sum_l += (long long) p.first * p.second;
            R.erase(p);
            L.insert(p);
        };

        vector<long long> ans(nums.size() - k + 1);
        for (int r = 0; r < nums.size(); r++) {
            // 添加 in
            int in = nums[r];
            del(in);
            cnt[in]++;
            add(in);

            int l = r + 1 - k;
            if (l < 0) {
                continue;
            }

            // 维护大小
            while (!R.empty() && L.size() < x) {
                r2l();
            }
            while (L.size() > x) {
                l2r();
            }
            ans[l] = sum_l;

            // 移除 out
            int out = nums[l];
            del(out);
            cnt[out]--;
            add(out);
        }
        return ans;
    }
};


int main(){
    vector<int> nums1={1,1,2,2,3,4,2,3}; Solution s; vector<int> ans1=s.findXSum(nums1,6,2); for(auto a: ans1) cout<<a<<" ";cout<<endl;

    vector<int> root={5,3,6,5,2,5,7,1,8,-1,-1,6,8};
    auto constructTree=[&](const vector<int>& nodes) -> TreeNode*{
        if (nodes.empty() || nodes[0] == -1) return nullptr;
        TreeNode* root = new TreeNode(nodes[0]);
        queue<TreeNode*> q;
        q.push(root);
        int i = 1;
        while (!q.empty() && i < nodes.size()) {
            TreeNode* current = q.front();
            q.pop();
            if (i < nodes.size() && nodes[i] != -1) {
                current->left = new TreeNode(nodes[i]);
                q.push(current->left);
            }
            i++;
            if (i < nodes.size() && nodes[i] != -1) {
                current->right = new TreeNode(nodes[i]);
                q.push(current->right);
            }
            i++;
        }
        return root;
    };
    function<void(TreeNode* root)> inorderTraversal=[&](TreeNode* root) -> void {
        if (root == NULL) return;
        inorderTraversal(root->left);
        cout << root->val << " ";
        inorderTraversal(root->right);
    };
    Solution2 s2; cout<<s2.kthLargePerfectSubtree(constructTree(root), 2)<<endl;

    Solution3 s3; cout<<s3.countWinningSeq("FFF")<<endl;

    vector<int> nums4={1,1,2,2,3,4,2,3};
    Solution4 s4; vector<ll> ans4=s4.findXSum(nums4, 6, 2); for(auto x: ans4) cout<<x<<" ";cout<<endl;
}